#include <bits/stdc++.h>

using namespace std;
struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL)
    {
    }
};
class Solution
{
public:
    TreeNode *pre;
    void inorder(TreeNode *&root)
    {
        if (!root)
        {
            return;
        }
        inorder(root->left);
        root->left = pre;
        if (pre)
        {
            pre->right = root;
        }
        pre = root;
        inorder(root->right);
    }
    TreeNode *Convert(TreeNode *pRootOfTree)
    {
        if (!pRootOfTree)
        {
            return pRootOfTree;
        }
        TreeNode *begin = pRootOfTree;
        while (begin->left)
        {
            begin = begin->left;
        }
        inorder(pRootOfTree);
        return begin;
    }
};
